package DP_983;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class Solution {
	int[] costs;
	Set<Integer> daySet;
	int[] memo;

	public int mincostTickets_memo(int[] days, int[] costs) {
		this.costs = costs;
		memo = new int[366];
		daySet = new HashSet<Integer>();
		for (int i : days) {
			daySet.add(i);
		}
	
		return dp(1);
	}

	private int dp(int day) {
		if (day > 365) {
			return 0;
		}

		if (memo[day] != 0) {
			return memo[day];
		}

		if (daySet.contains(day)) {
			memo[day] = Math.min(dp(day + 1) + costs[0], Math.min(dp(day + 7) + costs[1], dp(day + 30) + costs[2]));
		} else {
			memo[day] = dp(day + 1);
		}

		return memo[day];
	}
}
